#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <sstream>
#include <queue>
#include <algorithm>
using namespace std;
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
// 生成一棵树,返回的节点是树的根节点
#define OVERSIZE(_X_, CONTAINER) (_X_ >= CONTAINER.size())
TreeNode *create_tree(const std::string &str)
{

    std::vector<std::string> nums;

    std::istringstream sstream{
        std::string{str.begin() + 1, str.end() - 1} // 去除首位的中括号
    };

    for (std::string tmp; std::getline(sstream, tmp, ',');) // 分割字符串
    {
        if (!tmp.empty())
        {
            nums.emplace_back(tmp);
        }
    }

    constexpr char null_node[]{"null"};
    if (nums.empty())
    {
        return nullptr;
    }
    auto root = new TreeNode(std::stoi(nums.at(0)));
    if (1ull == nums.size())
    {
        return root;
    }

    std::queue<TreeNode *> q;
    q.push(root);
    size_t index = 1ull;
    while (!q.empty())
    {
        auto len = q.size();
        for (size_t i = 0ull; i < len; ++i)
        {
            auto tmp_node = q.front();
            q.pop();
            if (!OVERSIZE(index, nums) && nums.at(index) != null_node)
            {
                tmp_node->left = new TreeNode(std::stoi(nums.at(index)));
                q.push(tmp_node->left);
            }
            if (!OVERSIZE(index + 1, nums) && nums.at(index + 1) != null_node)
            {
                tmp_node->right = new TreeNode(std::stoi(nums.at(index + 1)));
                q.push(tmp_node->right);
            }
            index += 2;
        }
    }
    return root;
}
// TODO 树的打印,怎么也得看看吧
class TreePrint
{
public:
    int calDepth(TreeNode *root)
    {
        int res = -1;
        queue<TreeNode *> q;
        q.push(root);
        while (!q.empty())
        {
            int len = q.size();
            res++;
            while (len)
            {
                len--;
                auto t = q.front();
                q.pop();
                if (t->left)
                {
                    q.push(t->left);
                }
                if (t->right)
                {
                    q.push(t->right);
                }
            }
        }
        return res;
    }

    vector<vector<string>> printTree(TreeNode *root)
    {
        int height = calDepth(root);
        int m = height + 1;
        int n = (1 << (height + 1)) - 1;
        vector<vector<string>> res(m, vector<string>(n, ""));
        queue<tuple<TreeNode *, int, int>> q;
        q.push({root, 0, (n - 1) / 2});
        while (!q.empty())
        {
            auto t = q.front();
            q.pop();
            int r = get<1>(t), c = get<2>(t);
            res[r][c] = to_string(get<0>(t)->val);
            if (get<0>(t)->left)
            {
                q.push({get<0>(t)->left, r + 1, c - (1 << (height - r - 1))});
            }
            if (get<0>(t)->right)
            {
                q.push({get<0>(t)->right, r + 1, c + (1 << (height - r - 1))});
            }
        }
        return res;
    }
    void print_tree_to_stdout(TreeNode *root)
    {
        auto result = printTree(root);
        for (size_t i = 0; i < result.size(); i++)
        {
            for (size_t j = 0; j < result[0].size(); j++)
            {
                if (result[i][j] == "")
                {
                    cout << " ";
                }
                else
                {
                    std::cout << result[i][j];
                }
            }
            printf("\n");
        }
    }
};

// --------------------------------华丽的分割线-------------------------------------------

struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

// 函数实现
std::vector<std::vector<int>> parseNestedIntVectorString(const std::string &str)
{
    std::vector<std::vector<int>> result;
    std::string cleaned_str;

    // 1. 清理字符串：移除所有空格，并确保只有数字、逗号和方括号
    // 虽然 std::istringstream 可以处理空格，但手动清理可以使解析更稳定
    for (char c : str)
    {
        if (!std::isspace(c))
        {
            cleaned_str += c;
        }
    }

    if (cleaned_str.empty() || cleaned_str == "[]")
    {
        return result; // 处理空字符串或空的外层vector
    }

    // 检查是否以 "[[..." 或 "[..." 开头
    if (cleaned_str.length() < 2 || cleaned_str[0] != '[')
    {
        std::cerr << "Error: Invalid string format. Expected to start with '['." << std::endl;
        return {}; // 返回空，表示错误
    }

    // 移除最外层的方括号
    std::string inner_content = cleaned_str.substr(1, cleaned_str.length() - 2);

    // 使用 stringstream 来按逗号分隔每个内部向量的字符串表示
    std::istringstream iss(inner_content);
    std::string segment;

    while (std::getline(iss, segment, ']'))
    { // 以 ']' 作为分隔符，获取每个内部向量的片段
        // 清理 segment，移除前面的 ',' 和 '['
        size_t first_bracket = segment.find('[');
        if (first_bracket != std::string::npos)
        {
            segment = segment.substr(first_bracket + 1); // 从 '[' 之后开始
        }
        else if (!segment.empty() && segment[0] == ',')
        {
            segment = segment.substr(1); // 如果没有 '['，移除开头的 ','
        }

        // 移除所有不是数字或逗号的字符 (例如可能残留的空格或多余的逗号)
        std::string final_segment;
        for (char c : segment)
        {
            if (std::isdigit(c) || c == '-' || c == ',')
            { // 允许负号
                final_segment += c;
            }
        }

        if (final_segment.empty())
        {
            continue; // 跳过空的内部段 (例如 [[],[]] 中的空括号)
        }

        std::vector<int> inner_vec;
        std::istringstream inner_iss(final_segment);
        std::string num_str;

        while (std::getline(inner_iss, num_str, ','))
        { // 以 ',' 分隔数字
            try
            {
                inner_vec.push_back(std::stoi(num_str));
            }
            catch (const std::invalid_argument &e)
            {
                std::cerr << "Error: Invalid number format in segment '" << num_str << "'. " << e.what() << std::endl;
                // 可以选择在这里清空 inner_vec 或抛出异常
            }
            catch (const std::out_of_range &e)
            {
                std::cerr << "Error: Number out of range in segment '" << num_str << "'. " << e.what() << std::endl;
            }
        }
        result.push_back(inner_vec);
    }

    return result;
}

// 字符串转数组
// TODO 这部分代码有时间我要重写 少年啊,你永远没有时间
std::vector<int> stringToVector(std::string str)
{
    std::string input = str;
    std::vector<int> array;

    // Step 1: Remove square brackets
    input = input.substr(1, input.length() - 2);

    // Step 2: Split string by comma
    size_t pos = 0;
    std::string token;
    while ((pos = input.find(',')) != std::string::npos)
    {
        token = input.substr(0, pos);
        array.push_back(std::stoi(token));
        input.erase(0, pos + 1);
    }
    array.push_back(std::stoi(input)); // Add the last element

    // Print the resulting array
    return array;
}

ListNode *stringToListNode(const std::string &str)
{
    // 处理空字符串的情况
    if (str.empty())
    {
        return nullptr;
    }
    auto array = stringToVector(str);

    // 创建链表节点
    ListNode *dummyHead = new ListNode(); // 创建虚拟头节点
    ListNode *curr = dummyHead;
    for (int val : array)
    {
        curr->next = new ListNode(val);
        curr = curr->next;
    }

    // 返回实际的头节点
    ListNode *head = dummyHead->next;
    delete dummyHead; // 释放虚拟头节点的内存
    return head;
}
// 打印指针指向的链表,全部打印
void printListNode(ListNode *head)
{
    while (head != nullptr) // 可以才用汉语翻译的方法,可以方便的判断内容,容易的把逻辑和代码分离开
    {
        std::cout << head->val << " ";
        head = head->next;
    }
    printf("\n--------------\n");
}